package com.shuang.greed6;

public class Jump {

    //贪心：最少步数的最大覆盖范围
    public int jump(int[] nums) {

        //记录跳跃次数
        int count = 0;

        if (nums.length == 1){
            return count;
        }

        //记录当前覆盖范围
        int curRange = 0;

        //下一步的覆盖范围
        int nextRange = 0;

        for (int i = 0; i < nums.length; i++){
            //计算下一步覆盖范围(记录遍历数组时覆盖范围的最大值)
            nextRange = Math.max(nextRange, i + nums[i]);

            //覆盖范围大于等于数组最后一个数了
            if (nextRange >= nums.length - 1){
                //下一步覆盖范围够了 说明下一步就可以到达
                count++;
                break;
            }

            //覆盖范围还没达到 并且i遍历到当前覆盖范围最大了
            if (i == curRange){
                //此时要再继续往后走
                count++;
                curRange = nextRange;
            }
        }

        //最后返回count
        return count;
    }
}
